package leetcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class PermutationSequence {
	@Test
	public void testPerm(){
		PermutationSequence ps = new PermutationSequence();
		System.out.println(ps.getPermutation(3, 2));
	}
	
	public String getPermutation(int n, int k) {
		int[] pos = new int[n];
		getPerm(n, k, pos);
	
		List<Integer> l = new ArrayList<Integer>(n);
		int i = 1;
		while (i <= n)
			l.add(i++);

		StringBuilder b = new StringBuilder();
		for (int j = 0; j < pos.length; ++j)
			b.append(l.remove(pos[j]));

		return b.toString();
	}

	public void getPerm(int n, int k, int[] pos) {
		if (n == 0)
			return;

		int f = factorial(n - 1);
		for (int i = 0; i < n; ++i) {
			if (k <= (i + 1) * f) {
				pos[pos.length - n] = i;
				getPerm(n - 1, k - i * f, pos);
				return;
			}
		}
	}

	public int factorial(int n) {
		if (n == 0)
			return 1;

		int res = 1;
		while (n != 1)
			res *= n--;

		return res;
	}
}
